package consistent

import (
	"errors"
	"hash/crc32"
	"sort"
	"strconv"
	"sync"
)

//申明新的切片类型
type units []uint32

//返回切片长度
func (x units)Len()int  {
	return len(x)
}
//比较两个数的大小
func (x units)Less(i,j int)bool  {
	return x[i] < x[j]
}
//交换两个值的位置
func (x units)Swap(i,j int)  {
	x[i],x[j] = x[j],x[i]
}

//当Hash环上没有数据时，提示错误
var errEmpty = errors.New("Hash 环没有数据")
//创建结构体保存一致性Hash信息
type Consistent struct {
	//hash环key为hash值，存放的值时节点的信息
	circle map[uint32]string
	//已经排序的Hash切片
	sortedHasges units
	//虚拟节点个个数，用来增加hash的平衡性
	VirtualNode int
	//map 读写锁
	sync.RWMutex
}
//创建一致性hash算法结构体，设置默认节点数量
func NewConsistent()*Consistent  {
	return &Consistent{
		//初始化变量
		circle: make(map[uint32]string),
		//设置虚拟节点个数
		VirtualNode: 20,
	}
}
//自动生成key值
func (c *Consistent)generateKey(element string,index int)string  {
	return element+strconv.Itoa(index)
}
//获取hash位置
func (c *Consistent)hashkey(key string) uint32 {
	if len(key)<64{
		//声明一个数组长度为64
		var srcatch [64]byte
		//拷贝数据到数组中
		copy(srcatch[:],key)
		//使用Ieee多项式返回数据的CRC-32校验和
		return crc32.ChecksumIEEE(srcatch[:len(key)])
	}
	return crc32.ChecksumIEEE([]byte(key))
}
//更新排序方便查找
func (c *Consistent)updateSortedHashes()  {
	hashes := c.sortedHasges[:0]
	//判断切片容量，是否过大，如果过大则重置
	if cap(c.sortedHasges)/(c.VirtualNode*4) > len(c.circle){
		hashes = nil
	}
	//添加hashes
	for k := range c.circle{
		hashes = append(hashes,k)
	}
	//对所有节点hash值进行排序
	//方便之后进行二分查找
	sort.Sort(hashes)
	//重新赋值
	c.sortedHasges = hashes
}
//向hash环添加节点
func (c *Consistent)Add(element string)  {
	//加锁
	c.Lock()
	defer  c.Unlock()
	c.add(element)
}
//添加节点
func (c *Consistent)add(element string)  {
	//循环虚拟节点，设置副本
	for i:=0;i<c.VirtualNode;i++{
		c.circle[c.hashkey(c.generateKey(element,i))] = element
	}
	//更新排序
	c.updateSortedHashes()
}
//删除节点
func (c *Consistent)remove(element string)  {
	for i := 0;i<c.VirtualNode;i++{
		delete(c.circle,c.hashkey(c.generateKey(element,i)))
	}
	c.updateSortedHashes()
}
//删除一个节点
func (c *Consistent)Remove(element string)  {
	c.Lock()
	defer c.Unlock()
	c.remove(element)
}
//顺时针查找最近的节点
func (c *Consistent)search(key uint32)int  {
	//查找算法
	f := func(x int)bool {
		return c.sortedHasges[x] > key
	}
	//使用二分查找来搜索指定切片满足条件最小值
	i := sort.Search(len(c.sortedHasges),f)
	//如果超出范围则设置i=0
	if i >= len(c.sortedHasges){
		i = 0
	}
	return i
}
//根据数据标示获取服务器节点信息
func (c *Consistent)Get(name string)(string,error)  {
	//添加锁
	c.RLock()
	defer c.Unlock()
	//如果为零则返回错误
	if len(c.circle) == 0{
		return "",errEmpty
	}
	//计算hash值
	key := c.hashkey(name)
	i := c.search(key)
	return c.circle[c.sortedHasges[i]],nil
}